(defparameter *G* (make-hash-table))
(setf (gethash 'Arad *G*) '( (Zerind 75) (Sibiu 140) (Timisoara 118) ))
(setf (gethash 'Bucharest *G*) '( (Pitesti 101) (Giurgiu 90) (Fagaras 221) (Urziceni 85) ))
(setf (gethash 'Craiova *G*) '( (Dobreta 120) (Rimnichu-Vilcea 146) (Pitesti 138) ))
(setf (gethash 'Dobreta *G*) '( (Mehadia 75) (Craiova 120) ))
(setf (gethash 'Eforie *G*) '( (Hirsova 86) ))
(setf (gethash 'Fagaras *G*) '( (Sibiu 99) (Bucharest 211) ))
(setf (gethash 'Giurgiu *G*) '( (Bucharest 90) ))
(setf (gethash 'Hirsova *G*) '( (Urziceni 98) (Eforie 86) ))
(setf (gethash 'Iasi *G*) '( (Neamt 87) (Vaslui 92) ))
(setf (gethash 'Lugoj *G*) '( (Timisoara 111) (Mehadia 70) ))
(setf (gethash 'Mehadia *G*) '( (Lugoj 70) (Dobreta 75) ))
(setf (gethash 'Neamt *G*) '( (Iasi 87) ))
(setf (gethash 'Oradea *G*) '( (Zerind 71) (Sibiu 151) ))
(setf (gethash 'Pitesti *G*) '( (Craiova 138) (Rimnichu-Vilcea 97) (Bucharest 101) ))
(setf (gethash 'Rimnichu-Vilcea *G*) '( (Craiova 146) (Sibiu 80) (Pitesti 97) ))
(setf (gethash 'Sibiu *G*) '( (Oradea 151) (Arad 140) (Fagaras 99) (Rimnichu-Vilcea 80) ))
(setf (gethash 'Timisoara *G*) '( (Arad 118) (Lugoj 111) ))
(setf (gethash 'Urziceni *G*) '( (Bucharest 85) (Vaslui 142) (Hirsova 98) ))
(setf (gethash 'Vaslui *G*) '( (Urziceni 142) (Iasi 92) ))
(setf (gethash 'Zerind *G*) '( (Arad 75) (Oradea 71) ))
(setf cities '(Arad Bucharest Craiova Dobreta Eforie Fagaras Giurgiu
                   Hirsova Iasi Lugoj Mehadia Neamt Oradea Pitesti
                   Rimnichu-Vilcea Sibiu Timisoara Urziceni Vaslui Zerind ))

(setf N 20)
(setf *used* (make-hash-table :size N))
; (loop for node in cities do
;   (format t "~% ~d ~d ~d" node (gethash node *used*) (gethash node *G*))
; )

(defvar path '())
(defvar *S* 'Bucharest)
(defvar *T* 'Pitesti)

(defun bfs(tree)
  (let ( (Q (list (list tree 0)) ) )
    (loop while (not (null Q)) do
      (let ((node (car Q)))
        (print Q)
        (setf Q (cdr Q))
        (loop for to in (gethash (car node) *G*) do
          (when (null (gethash (car to) *used*))
            (setf Q (append Q (list (list (car to) (+ (cadr to) (cadr node))))))
            (setf (gethash (car to) *used*) t)
            ; (format t "~%  ~S->~S" to Q)
          )
        )
      )
    )
  )
)

(bfs 'Bucharest)
